package sort.quickly;

import sort.common.PrintArr;
import sort.common.SortClass;

/**
 * 三路快速排序
 * [startIndex,endIndex]之间，
 * arr[startIndex]为基准值
 
 * [startIndex,lt] ---小于基准值的数
 * [lt+1,gt-1] ---等于基准值的数
 * [gt,endIndex] --大于基准值的数
 * 维护两个变量lt，gt
 */
public class QuickSort3Way extends PrintArr implements SortClass {

    @Override
    public void sort(int[] arr) {
        quickSort3(arr,0,arr.length-1);
    }

    private void quickSort3(int[] arr,int startIndex,int endIndex){
        if (startIndex>=endIndex){
            return;
        }

        //注意lt和gt的初始值
        int lt = startIndex,gt = endIndex+1, compareVal = arr[startIndex],index = startIndex+1;
        while ( index!=gt ){
            if (arr[index]>compareVal){
                swapNum(arr,index,gt-1);
                gt--;
            }else if (arr[index]<compareVal){
                swapNum(arr,index,lt+1);
                lt++;
                index++;
            }else {
                index++;
            }
        }

        //最后将基准调换，交换lt和基准值
        arr[startIndex] = arr[lt];
        arr[lt] = compareVal;

        quickSort3(arr,startIndex,lt);
        quickSort3(arr,gt,endIndex);

    }

    private void swapNum(int[] arr,int index1,int index2){
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    public static void main(String[] args) {
        int arr[] = new int[]{4, 2, 1, 5, 7, 11, 32, 43, 22, 15}, arr2[] = new int[]{3,3,3,7,9,122344,4656,34,34,4656,5,6,7,8,9,343,57765,23,12321};

        QuickSort3Way sort3Way = new QuickSort3Way();
        sort3Way.sort(arr);
        sort3Way.printArr(arr);

        sort3Way.sort(arr2);
        sort3Way.printArr(arr2);
    }
}
